package com.lqian.simplestructure.sorted;

import java.util.Arrays;

/**
 * 插入排序
 *1. 将数组中的数据分为两个区间，已排序区间和未排序区间。初始已排序区间只有一个元素，就是数组的第一个元素。
 *    插入算法的核心思想就是取未排序区间中的元素，在已排序区间中找到合适的插入位置将其插入，并保证已排序区间数据一直有序
 *    重复这个过程，直到未排序区间中的元素为空，算法结束
 *
 * 2. 插入排序也包含两种操作，一种是元素的比较，一种是元素的移动。
 *    当我们需要将一个数据a插入到已排序区间时，需要拿a与已排序区间的元素依次比较大小，找到合适的插入位置，找到插入点后，我们还
 *    需要将插入点之后的元素顺序往后移动一位，这样才能腾出位置给元素a插入。
 *
 *    属于原地排序,空间复杂度为O(1)
 *    可以保持原有元素的前后顺序不变，属于稳定的排序算法
 *    时间复杂度分析：
 *          1) 如果排序的数组已经是有序的，我们并不需要搬移任何数据，如果我们从尾到头，在有序数组里面查找插入位置，每次只需要比较一个数据就能确定插入的位置。
 *          所以这种情况下，时间复杂度为O(n)
 *          2）如果数组是倒序的，每次插入都相当于在数组的第一个位置插入新的数据，所以需要移动大量的数据，所以最坏情况时间复杂度为O(n^2)
 *          3）在数组中插入一个数据的平均时间复杂度是O(n)
 *             对于插入排序来说，每次插入操作相当于在数组中插入一个数据，循环执行n次插入操作，所以平均时间复杂度为O(n^2)
 */
public class InsertSort {

    public static void main(String[] args) {
        int[] arr = {4,5,6,1,3,2};
        System.out.println(Arrays.toString(arr));
        insertSort(arr,arr.length);
        System.out.println(Arrays.toString(arr));
    }

    //arr 表示数组 n 表示数组长度
    public static void insertSort(int[] arr,int n){
        // 如果只有一个
        if (n <= 1) return;


        for (int i = 1;i < n;i++){
            // i= 1 从第二位开始
            int value = arr[i];
            // 指向i的前面元素
            int j = i - 1;
            //检查所有前面已排好序的元素，查找插入的位置
            for (; j >= 0; --j){
                if (arr[j] > value){    //所有大于value的元素都向后挪位
                    arr[j+1] = arr[j]; //数据移动
                }else{
                    break;
                }
            }
            arr[j+1] = value; //插入元素 // j--  ==> -1;
        }
    }
}
